/**
 * 快排，平均时间复杂度O(nlogn)
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
    sortColor(nums, 0, nums.length - 1)
};

const sortColor = (nums, left, right) => {
    if (left < right) {
        let i = splitNums(nums, left, right)
        sortColor(nums, left, i - 1)
        sortColor(nums, i + 1, right)
    }
}

const splitNums = (nums, left, right) => {
    let val = nums[right],
        temp = left;

    for (let i = left; i < right; i++) {
        if (nums[i] < val) {
            [nums[i], nums[temp]] = [nums[temp], nums[i]]
            temp++
        }
    }
    [nums[temp], nums[right]] = [nums[right], nums[temp]]
    return temp
}


/**
 * 双指针。p0为查到0时，交换值，移动指针；p1为查到0和1时，交换值，移动指针
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
    let numsLen = nums.length,
        p0 = 0, p1 = 0;

    for (let i = 0; i < numsLen; i++) {
        if (nums[i] === 1) {
            [nums[i], nums[p1]] = [nums[p1], nums[i]]
            p1++
        } else if (nums[i] === 0) {
            // 此次交换可能是0和1的交换
            [nums[i], nums[p0]] = [nums[p0], nums[i]]
            // 目前p1为大于1的坐标最大值
            if (p0 < p1) {
                [nums[i], nums[p1]] = [nums[p1], nums[i]]
            }
            p0++
            p1++
        }
    }
};